package wwl.lsf;

import wwl.lsf.base.ListNode;

import java.util.PriorityQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/5/27
 * @Description
 */
public class 合并两个有序链表 {

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        PriorityQueue<ListNode> lists = new PriorityQueue<>((x, y) -> x.val - y.val);

        lists.add(l1);
        lists.add(l2);
        ListNode yade = new ListNode(0);

        ListNode temp = yade;
        while (!lists.isEmpty()) {

            ListNode peek = lists.poll();
            temp.next = peek;
            if (peek.next != null) {
                lists.add(peek.next);
            }
            temp = peek;
        }

        return yade.next;


    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5);
        ListNode listNode3 = new ListNode(3, listNode5);
        ListNode listNode1 = new ListNode(1, listNode3);


        ListNode listNode6 = new ListNode(6);
        ListNode listNode4 = new ListNode(4, listNode6);
        ListNode listNode2 = new ListNode(2, listNode4);

        ListNode youxianjiduilie = mergeTwoListsziji(listNode1, listNode2);

        while (youxianjiduilie != null) {
            System.out.println("youxianjiduilie = " + youxianjiduilie.val);
            youxianjiduilie = youxianjiduilie.next;
        }
    }

    public static ListNode mergeTwoListsziji(ListNode l1, ListNode l2) {

        ListNode pre4Result = new ListNode(-1);

        ListNode begin = pre4Result;

        while (l1 != null && l2 != null) {

            if (l1.val < l2.val) {
                begin.next = l1;
                l1 = l1.next;
            } else {
                begin.next = l2;
                l2 = l2.next;
            }

            begin = begin.next;
        }

        begin.next = l1 == null ? l2 : l1;

        return pre4Result.next;

    }
}
